package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         81,
		Discription: "搜索存在重复元素的有序旋转数组",
		Level:       2,
		Labels: map[string]int{
			"二分查找": 1,
			"去重":   1,
		},
	})
}

func Search2(nums []int, target int) bool {
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := (left + right) / 2
		if nums[mid] == target {
			return true
		}

        //left==mid或mid==right时会干扰判断，需要去重
		for left < mid && nums[mid] == nums[left] {
			left++
		}
		for mid < right && nums[mid] == nums[right] {
			right--
		}

        //该有等号的地方都得有等号，考虑到半边只剩下一个数字的情况
		if nums[left] <= nums[mid] {
			if nums[left] <= target && target<=nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			if nums[mid] <= target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}

	return false
}
